package string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * O(n+m) average
 * 
 * @author yinzichen
 * 
 */
public class RabinKarp {

	public HashMap<String, ArrayList<Integer>> rabinKarp(String text,
			Set<String> patterns, int m) {
		HashMap<String, ArrayList<Integer>> match = new HashMap<String, ArrayList<Integer>>();
		for (String pattern : patterns) {
			match.put(pattern, new ArrayList<Integer>());
		}
		int n = text.length();
		if (n < m) {
			return match;
		}
		int hsize = patterns.size() << 4, d = 256, h = 1;
		hsize = 10001;
		boolean[] hash = new boolean[hsize];
		for (int i = 1; i < m; ++i) {
			h = (h * d) % hsize;
		}
		int hv;
		for (String p : patterns) {
			hv = 0;
			for (int i = 0; i < m; ++i) {
				hv = (hv * d + p.charAt(i)) % hsize;
			}
			hash[hv] = true;
		}
		hv = 0;
		for (int i = 0; i < m; ++i) {
			hv = (hv * d + text.charAt(i)) % hsize;
		}
		String sub = text.substring(0, m);
		if (hash[hv] && patterns.contains(sub)) {
			match.get(sub).add(0);
		}
		for (int i = m; i < n; ++i) {
			hv = ((hv - h * text.charAt(i - m)) * d + text.charAt(i)) % hsize;
			hv = (hv + hsize) % hsize;
			sub = text.substring(i - m + 1, i + 1);
			if (hash[hv] && patterns.contains(sub)) {
				match.get(sub).add(i - m + 1);
			}
		}
		return match;
	}

	public static void main(String[] args) {
		Set<String> patterns = new HashSet<String>();
		patterns.add("aba");
		patterns.add("bab");
		patterns.add("abb");
		patterns.add("bba");
		RabinKarp a = new RabinKarp();
		HashMap<String, ArrayList<Integer>> res = a.rabinKarp(
				"bbabbababbaabbbabbb", patterns, 3);
		for (String s : res.keySet()) {
			System.out.println(s + " " + res.get(s).size());
		}
	}

}
